#include <sstream>
class Solution {
public:
    char* Serialize(TreeNode* root) {    
        ostringstream oss;
        serializeHelper(root, oss);
        string str = oss.str();
        char* res = new char[str.length()+1];
        strcpy(res, str.c_str());
        return res;
    }

    void serializeHelper(TreeNode* root, ostringstream& oss) {
        if (!root) {
            oss << "# ";
            return;
        }
        oss << root->val << " ";  
        serializeHelper(root->left, oss);
        serializeHelper(root->right, oss);
    }

    TreeNode* Deserialize(char* str) {
        istringstream iss(str);
        return deserializeHelper(iss);
    }

    TreeNode* deserializeHelper(istringstream& iss) {
        string ch;
        iss >> ch;
        if (ch == "#") {
            return nullptr;
        }
        int val = stoi(ch);
        TreeNode* root = new TreeNode(val);
        root->left = deserializeHelper(iss);
        root->right = deserializeHelper(iss);
        return root;
    }
};